package leetcode;

import java.util.ArrayList;
import java.util.List;

import Tree.BinaryTreeCreate;
import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class RecoverBinarySearchTree {

	public static void main(String[] args) {
		int[] in = {9, 3, 10, 12, 16};
		int[] pre = {12, 3, 9, 10, 16};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		
		RecoverBinarySearchTree object = new RecoverBinarySearchTree();
		object.recoverTree(root);
		
		BinaryTreeCreate.inOrder(root);
		BinaryTreeCreate.preOrder(root);
	}
	
	
	// 我想到的方法可能比较简单，就是中序遍历，因为我们知道二叉搜索树中序遍历是有序的
	//bad idea, 10ms, beat 5.9%
	List<Integer> list = new ArrayList<>();

	public void recoverTree(TreeNode root) {
		list.clear();
		getValues(root);
		int length = list.size();
		int index1 = -1, index2 = -1;
		int index3 = -1, index4 = -1;
		for (int i = 1; i < length; i++) {
			//找逆序对
			//可能有10 9 3 12 14
			//此时是3和10的位置反了
			//也可能有9 3 10 12 14，此时是3和9的位置反了
			if (list.get(i) < list.get(i - 1)) {
				if (index1 == -1) {
					index1 = i - 1;
					index2 = i;
				} else {
					index3 = i - 1;
					index4 = i;
				}
			}
		}
		System.out.println("index1 " + index1 + " index3 " + index3);
		if(index3 == -1){
            changeValues(root, list.get(index1), list.get(index2), false, 
            		list.get(index2), list.get(index1), false);
        }else if(index1 != -1){
            changeValues(root, list.get(index1), list.get(index4), false, 
            		list.get(index4), list.get(index1), false);
        }
	}

	public void getValues(TreeNode node) {
		if (node == null) {
			return;
		}
		getValues(node.left);
		list.add(node.val);
		getValues(node.right);
	}

	public void changeValues(TreeNode root, int val, int changeVal, boolean flag1, 
			int val2, int changeVal2, boolean flag2) {
		if (root == null) {
			return;
		}
		if(flag1 && flag2 ){
            return;
        }
        if(root.val == val){
            flag1 = true;
            root.val = changeVal;
        }else if(root.val == val2){
            flag2 = true;
            root.val = changeVal2;
        }
        changeValues(root.left, val, changeVal, flag1, val2, changeVal2, flag2);
        changeValues(root.right, val, changeVal, flag1, val2, changeVal2, flag2);
	}
}
